#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//int main()
//{
//	int n = 0;
//	while (scanf("%d", &n) != EOF)
//	{
//		printf("%d\n", Fibonacci(n));
//	}
//	return 0;
//}
//int Fibonacci(int n)
//{
//	if (n <= 2)
//		return 1;
//	return Fibonacci(n - 1) + Fibonacci(n - 2);
//}
//#include <stdio.h>
//int main()
//{
//	int a[10] = { 0 };
//	int i;
//	int len = sizeof(a) / sizeof(int);
//	for (i = 0; i < len; i++)
//	{
//		printf("%p\n", &a[i]);
//	}
//	return 0;
//}
//#include<stdio.h>
//int Fibonacci(int n);
//int main()
//{
//	int n = 0;
//	while (scanf("%d", &n) != EOF)
//	{
//		printf("%d\n", Fibonacci(n));
//	}
//	return 0;
//}
//int Fibonacci(int n)
//{
//	if (n <= 2)
//		return 1;
//	int a = 1;
//	int b = 1;
//	int c = 0;
//	while (n-- > 2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//	}
//	return c;
//}
//#include<stdio.h>
//int factorial(int n);
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	printf("%d", factorial(n));
//	return 0;
//}
//int factorial(int n)
//{
//	if (n == 1)
//		return 1;
//	return n * factorial(n - 1);
//}
//#include<stdio.h>
//int main()
//{
//	int n, k;
//	while (scanf("%d%d",&n,&k)!=EOF)
//	{
//		printf("%d", pow(n, k));
//	}
//	return 0;
//}
//int pow(int n, int k)
//{
//	if (k == 1)
//		return n;
//	return n * pow(n, k - 1);
//}
//#include<stdio.h>
//int Digitsum(int n);
//int main()
//{
//	int n;
//	while (scanf("%d", &n) != EOF)
//	{
//		printf("%d", Digitsum(n));
//	}
//	return 0;
//}
//int Digitsum(int n)
//{
//	if (n < 9)
//		return n % 10;
//	return n % 10 + Digitsum(n / 10);
//}
//#include<stdio.h>
//int main()
//{
//
//	return 0;
//}
//void reserve_string(char* str,int len)
//{
//	int start = 0;
//}